import java.util.Arrays;

public class J101501 {
    // 插入排序
    public static void insertSort(int[] array){
        for(int i = 0; i < array.length - 1; i++){
            int num = array[i + 1];
            for(int k = 0; k <= i; k++){
                if(num < array[k]){
                    moveBack(array, k, i);
                    array[k] = num;
                    break;
                }
            }
        }
    }
    //希尔排序
    public static void shellSort(int[] array){
        int gap = (array.length - 1) / 2;
        while(gap > 0) {
            for (int i = 0; i < array.length - 1; i += gap) {
                int num = array[i + 1];
                for (int k = 0; k <= i; k++) {
                    if (num < array[k]) {
                        moveBack(array, k, i);
                        array[k] = num;
                        break;
                    }
                }
            }
            gap /= 2;
        }
    }

    public static void moveBack(int[] arr, int start, int end){
        while(end >= start){
            arr[end + 1] = arr[end--];
        }
    }

    public static void main(String[] args) {
        int[] test = new int[]{5,9,8,3,6,2,4,1,7,0};
        shellSort(test);
        System.out.println(Arrays.toString(test));
    }
}
